"""
时间复杂度：O(nlogn)
"""
import time
import random
import sys

from SortingAlgorithm.cal_time.cal_time import cal_time

# def cal_time(fn):
#
#     def wrapper(*args, **kwargs):
#         start = time.time()
#         ret = fn(*args, **kwargs)
#         end = time.time()
#         delta = end - start
#         print("自己写的:", delta)
#         return ret
#     return wrapper


@cal_time(name="快速排序时间")
def quick_sort(arr):
    _quick_sort(arr)


# 快速排序
def _quick_sort(arr, _l=None, _r=None):
    '''
    :param arr: 要排序的列表
    :param _l:  最左边指针
    :param _r:  最右边指针
    :return:
    '''
    if _l is None and _r is None:
        _l, _r = 0, len(arr)-1

    l, r, t = _l, _r, 0
    if r - l > 0:
        index = l + (r-l) // 2  # 不取第一个元素为比较值, 而是取中间元素来当比较值，为的就是避免最坏的情况出现，导致变成O(n**2), 同时也很有可能超出递归深度
        arr[_l], arr[index] = arr[index], arr[_l]
        t = arr[_l]
        while l < r:
            while l < r and arr[r] >= t:
                r = r - 1
            arr[l] = arr[r]
            while l < r and arr[l] <= t:
                l = l + 1
            arr[r] = arr[l]
        arr[r] = t
        _quick_sort(arr, _l, l-1)
        _quick_sort(arr, l+1, _r)


if __name__ == '__main__':
    # 生成十万第有序的列表
    li = list(range(100000))
    # 打乱顺序
    random.shuffle(li)

    quick_sort(li)

    random.shuffle(li)

    start = time.time()
    # sorted(li)
    li.sort()
    delta = time.time() -start
    print("python内置排序模块:", delta)
